package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序：------（无论什么数据进去都是 O(n²) 的时间复杂度）
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * <p>
 * 重复第二步，直到所有元素均排序完毕。
 * 1.选择排序有“数组大小 - 1”次排序（循环）
 * 2.前面的元素与其后面的元素比较并交换
 *
 * @author: 蔡奇峰
 * @date: 2020/7/18 17:03
 **/
public class SelectSort {


    public static void main(String[] args) {
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};
        int[] arr = new int[7780];
        for (int i = 0; i < 7780; i++) {

            arr[i] = new Random().nextInt(1800);
        }
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
        sort(arr);
        long timeMilli = System.currentTimeMillis();

        System.out.println("数组排序后：" + Arrays.toString(arr));

        System.out.println("选择排序耗时：" + (timeMilli - timeMillis));
    }

    /**
     * 选择排序：前一个与后面逐个进行比较，将最小的放到前面。
     *
     * @param arr 需要排序的数组
     */
    public static void sort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            // 最小值的索引，默认是前面元素
            int minIndex = i;
            // 最小值，默认是前面元素
            int minValue = arr[i];

            // 与后面的进行比较
            for (int j = i + 1; j < arr.length; j++) {
                // 比较大小，得到最小的值、下标
                if (minValue > arr[j]){
                    minIndex = j;
                    minValue = arr[j];
                }
            }
            // 如果最小值不是默认的元素则交换
            if (minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = minValue;
            }
        }
    }

}
